Грејов код
| време | меморија | улаз | излаз |
|---|---|---|---|
| 1 s | 64 Mb | стандардни излаз | стандардни улаз |
Грејов кôд реда \(n\) подразумева ређање свих \(n\)-тоцифрених бинарних записа тако да се свака два суседна записа разликују тачно у једном биту (при чему ово важи и за први и последњи запис, тако да се може сматрати да су сви записи поређани у круг).
Грејов кôд дужине \(0\) садржи само један елемент и то празну ниску. Грејов кôд дужине \(n+1\) се може добити од кода дужине \(n\) тако што се испред сваког броја у коду дужине \(n\) допише цифра \(0\), затим се редослед елемената у коду дужине \(n\) обрне и на сваком броју се на почетак допише цифра \(1\) и два тако добијена низа бројева се споје. Нпр. Грејов кôд реда \(2\) је
00 01 11 10
На основу претходног поступка добијамо Грејов кôд реда \(3\).
0 00 | k 0 01 | 0: 000 0 11 | 1: 001 0 10 v 2: 011 tj. 3: 010 1 10 ^ 4: 110 1 11 | 5: 111 1 01 | 6: 101 1 00 | 7: 100
Заиста, у коду дужине \(n+1\) бројеви у првој половини сви почињу нулом, па се разликују тачно у биту у ком се разликују одговарајући кодови у Грејовом коду дужине \(n\), бројеви у другој половини сви почињу јединицом, па и за њих важи исто, док се последњи број прве и први број друге половине разликују само на почетном биту, а исто важи и за први број прве и последњи број друге половине.
Напиши програм који за дату дужину кода \(n\) и дату позицију \(k\) (\(0 \leq k < 2^n\)) одређује бинарни број који се налази на позицији \(k\) у коду дужине \(n\).
Улаз
Са стандардног улаза се учитава дужина кода \(n\) (\(1 \leq n \leq 32\)) и позиција \(k\) (\(0 \leq k < 2^n\)).
Излаз
На стандардни излаз исписати тражени бинарни број.
Пример 1
Улаз
3 2
Излаз
011
Пример 2
Улаз
30 999999999
Излаз
100110010101111010110100000000
Морате бити улоговани како бисте послали задатак на евалуацију.